package tencent_practice;

/**
 * 爬楼梯，斐波那契数列
 * 直接使用通项公式
 * 或者使用动态规划
 * 通项公式
 * double sqrt5 = Math.sqrt(5);
 * double a = Math.pow((1 + sqrt5) / 2, n + 1) + Math.pow((1 - sqrt5) / 2, n + 1);
 * return (int) Math.round(a / sqrt5);
 *
 * Math.pow()：平方函数
 * Math.sqrt()：开平方函数
 * Math.round()：传入float，得到一个int；传入double，得到long
 */
public class Tencent_70_climbStairs {
    /**
     * 通项公式
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        double sqrt5 = Math.sqrt(5);
        double a = Math.pow((1 + sqrt5) / 2, n + 1) + Math.pow((1 - sqrt5) / 2, n + 1);
        return (int)Math.round(a / sqrt5);
    }

    public int climbStairs(int n, boolean noUse) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        if (n == 3) {
            return 3;
        }
        int q = 2, p = 3, r = 0;
        for (int i = 4; i <= n; i++) {
            r = q + p;
            q = p;
            p = r;
        }
        return p;
    }
}
